package Leetcode.图;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/9/12 17:11
 * @Description:
 * 你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。
 *
 * 同时给你一个字符串数组 supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。
 *
 * 请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。
 *
 * 注意两道菜在它们的原材料中可能互相包含。
 * 示例 1：
 *
 * 输入：recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
 * 输出：["bread"]
 * 解释：
 * 我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
 * 示例 2：
 *
 * 输入：recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
 * 输出：["bread","sandwich"]
 * 解释：
 * 我们可以做出 "bread" ，因为我们有原材料 "yeast" 和 "flour" 。
 * 我们可以做出 "sandwich" ，因为我们有原材料 "meat" 且可以做出原材料 "bread" 。
 */

public class 给定原材料中找到所有可以做出的菜 {
    public List<String> findAllRecipes(String[] recipes,List<List<String>> ingredients, String[] supplies) {
        List<String> res=new ArrayList<>();
        boolean[] isComplete=new boolean[recipes.length];//isComplete[i]=true标识第i个菜已经完成
        boolean isAllDo=true;//当为false时说明完成可以制作的全部菜
        //添加原材料
        //保存现有的原材料
        Set<String> set = new TreeSet<>(Arrays.asList(supplies));
        while (isAllDo) {
            int befLen=set.size();
            for (int i = 0; i < ingredients.size(); i++) {
                if (isComplete[i]) {
                    continue;//如果该菜已经完成，则直接跳过本次循环，减速时间浪费
                }
                List<String> tmp = ingredients.get(i);//制作本次菜品所需的原材料
                boolean flag = true;//为true说明可以制作本次菜品
                for (String s : tmp) {
                    if (!set.contains(s)) {//无法制作本次菜品，直接跳出
                        flag = false;//修改为false，不可以制作本次菜品
                        break;
                    }
                }
                if (flag) {//为true说明可以制作本次菜品
                    set.add(recipes[i]);//本次菜品添加为原材料
                    res.add(recipes[i]);//本次菜品添加返回
                    isComplete[i] = true;//标记第i个菜品已经制作完成
                }
            }
            //如果原材料不在继续增长，则说明剩下的菜品都无法则作，跳出循环
            if (set.size() <= befLen) {
                isAllDo = false;
            }
        }
        return res;
    }
}
